package DataStructure.tree;

public class BinaryTree2<Key extends Comparable<Key>,Value> {
    private Node root;
    private int N;

    private class Node{
        public Node left;
        public Node right;
        public Key key;
        public Value value;

        public Node(Key key,Value value,Node left,Node right){
            this.key=key;
            this.value= value;
            this.left= left;
            this.right=right;
        }


    }



    public int size(){
        return N;
    }

    //如果根节点为空，则将插入的元素替换为根节点
    public void put(Key key,Value value){
        root = put(root,key,value);
    }

    //向指定的树x中添加并返回添加元素后新的树
    public Node put(Node x,Key key,Value value){
        //如果x子树为空
        if(x==null){
            N++;
            return new Node(key,value,null,null);
        }
        int cmp= key.compareTo(x.key);
        if(cmp>0){
            //如果key大于x节点的键，则继续找x的右子树
            x.right = put(x.right,key,value);
        }else if(cmp<0){
            //如果key小于x节点的键，则继续找x的左子树
            x.left = put(x.left,key,value);
        }else {
            //如果key等于x节点的键，则替换x的value
            x.value=value;
        }

        return x;
    }


    //查询整个数中key对应的value
    public Value get(Key key){
        Value value = get(root,key);
        return value;
    }

    //查询x树中key对应的value
    public Value get(Node x,Key key){
        //x树为null
        if(x==null){
            return null;
        }
        int cmp=key.compareTo(x.key);
        if(cmp>0){
            return get(x.right,key);
        }else if(cmp<0){
            return get(x.left,key);
        }else {
            return x.value;
        }
    }









    //删除整个树中key对应的结点
    public void delete(Key key){
        delete(root,key);
    }

    //删除指定树中key对应的结点,并返回
    public Node delete(Node x,Key key){
        //x为null
        if(x==null){
            return null;
        }

        //x不为null
        int cmp=key.compareTo(x.key);
        if(cmp>0){
            //删除x右子树键为key的结点并把删除结点后的x右子树返回成为x的右子树
            x.right = delete(x.right,key);
        }else if(cmp<0){
            x.left = delete(x.left,key);
        }else {
            N--;
            //找到右子树中最小的结点
            if(x.right==null){
                return x.left;
            }
            if(x.left==null){
                return x.right;
            }
            //如果x的左右都不为空，则找到x的右子树的最小值代替x
            Node minNode=x.right;
            while (minNode.left!=null){
                minNode=minNode.left;
            }
            //删除minNode
//            Node n=x.right;
//            while (n.left!=null){
//                if(n.left.left==null){
//                    n.left=null;
//                }else {
//                    n=n.left;
//                }
//            }
            Node n=x.right;
            while (n.left!=null){
                if (n.left.left==null && n.left.right==null){
                    n.left=null;
                    break;
                }else if(n.left.left==null && n.left.right!=null){
                    n.left=n.left.right;
                    break;
                }else {
                    n=n.left;
                }
            }

            minNode.left=x.left;
            minNode.right=x.right;
            x=minNode;
        }
        return x;
    }


}
